#include <bits/stdc++.h>
using namespace std;
void run_case() {
  string S;
  cin >> S;
  int N = int(S.size());
  int zeros = int(count(S.begin(), S.end(), '0'));  // 总共的 0 数
  int ones = int(count(S.begin(), S.end(), '1'));   // 总共的 1 数
  assert(zeros + ones == N);
  vector<int> prefix(N + 1, 0);  // 前缀中 1 的个数

  for (int i = 0; i < N; i++) prefix[i + 1] = prefix[i] + (S[i] - '0');

  int best =
      min(zeros, ones);  // 0 1 之间最小的那个数，答案不会更小了（为什么）

  for (int i = 0, j = 0; i < N; i++) {
    while (j < N &&
           // 区间长度 - 区间内 1 的个数 = 区间内 0 的个数
           j - i - (prefix[j] - prefix[i]) <
               // 总共 1 的个数 - 区间内 1 的个数 = 区间外 1 的个数
               ones - (prefix[j] - prefix[i]))
      j++;  // 区间内 0 的个数比区间外 1 的个数少
    // O(N^2) 我为什么当场就把 N^2 做法废掉了...

    best = min(best, max(
                         // 区间长度 - 区间内 1 的个数 = 区间内 0 的个数
                         j - i - (prefix[j] - prefix[i]),
                         // 总共 1 的个数 - 区间内 1 的个数 = 区间外 1 的个数
                         ones - (prefix[j] - prefix[i])));
  }

  cout << best << '\n';
}

int main() {
  int tc;
  cin >> tc;
  while (tc--) run_case();
}
